Flash memory devices are well known in the art, see for example U.S. Pat. No. 6,988,175 to Lasser, which is incorporated herein by reference. FIG. 1A is a high level schematic block diagram of a generic, prior art flash-based data storage device 10 shown therein. Device 10 is used by a host device (not shown) for storing data in one or more NAND flash media 12. The operation of device 10 is controlled by a microprocessor-based controller 14 with the help of a random access memory (RAM) 16 and an auxiliary non-volatile memory 18. For this purpose, flash device 10 and the host system communicate via a communication port 20 in flash device 10. Typically, for backwards compatibility with host devices whose operating systems are oriented towards block memory devices such as magnetic hard disks, flash device 10 emulates a block memory device, using firmware stored in auxiliary non-volatile memory 18 that implements flash management methods such as those taught by Ban in U.S. Pat. Nos. 5,404,485 and 5,937,425, both of which patents are incorporated by reference for all purposes as if fully set forth herein. The components of device 10 are housed together in a common housing 15.
Other devices that use NAND flash media to store data are known. FIG. 1B, also taken from U.S. Pat. No. 6,988,175, shows such a prior art device, a personal computer 10′ in which NAND flash media 12 are used in addition to, or as a substitute for, a magnetic hard disk for long-term non-volatile data storage. Controller 14 now represents the central processing unit of personal computer 10′. Auxiliary non-volatile memory 18 now represents all of the other non-volatile memories of personal computer 10′, including a BIOS in which boot code is stored and a magnetic hard disk for storing the operating system, including the flash management system, of personal computer 10′ (unless NAND flash media 12 are a substitute for a magnetic hard disk, in which case the operating system is stored in NAND flash media 12). NAND flash media 12, controller 14, RAM 16, auxiliary non-volatile memory 18 and other components (not shown) of personal computer 10′ communicate with each other via a bus 19. In some configurations of personal computer 10′, NAND flash media 12 are on a removable card. In other configurations of personal computer 10′, the illustrated components are integrated in a single unitary physical device, so that NAND flash media 12 are not a physically separate entity.
The operations that controller 14 performs on NAND flash media 12 include read operations, write operations and erase operations. NAND Flash media 12 typically are written in units called “pages”, each of which typically includes between 512 bytes and 2048 bytes, and typically are erased in units called “blocks”, each of which typically includes between 16 and 64 pages. Note that the use of the word “block” to refer to the erasable units of NAND flash media 12 should not be confused with the use of the word “block” in the term “block memory device”. The “block” nature of a block memory device refers to the fact that the device driver exports an interface that exchanges data only in units that are integral multiples of a fixed-size unit that typically is called a “sector”.
To facilitate the management of NAND flash media 12, controller 14 assigns each page a status of “unwritten” or “written”. A page whose status is “unwritten” is a page that has not been written since the last time it was erased, and so is available for writing. A page whose status is “written” is a page to which data have been written and not yet erased. In some embodiments of device 10, controller 14 also assigns some pages a status of “deleted”. A page whose status is “deleted” is a page that contains invalid (typically superseded or out of date) data. In embodiments of device 10 that support “deleted” pages, the “written” status is reserved for pages that contain valid data. A page whose status is “unwritten” is called an “unwritten page”, a page whose status is “written” is called a “written page” and a page whose status is “deleted” is called a “deleted page”.
Because device 10 is used for non-volatile data storage, it is vital that device 10 retain the data written thereto under all circumstances. A major risk to the integrity of data stored in device 10 is a sudden power failure in which the power source to device 10 is interrupted with no prior notice while device 10 is in the middle of an operation. Often such a power failure causes the interrupted operation to have erratic or unpredictable results.
The problem of data loss in flash memory systems due to power interruption is well known in the art of non-volatile memory systems, and described in detail in U.S. Pat. No. 6,988,175. Write operations can be interrupted by power loss before the logical state of a cell has changed from “1” to “0”, resulting in pages defined herein as “interrupted” pages. Although interrupted pages may seem ready to be written, as they have not been written since the last time their block was erased, in actuality, some of their cells are “almost turned to logical 0”. In flash memory, following such an event, the stored data in such pages is not only unpredictable but also unreliable, as an interrupted write operation leaves the data in a non-stable state. The logical state may seem correct, but if cells that are supposed to be “0” are already written with electrons from the interrupted write operation, the logical state may change spontaneously over time. The following example shows how an interrupted write process can cause a problem.
If a sequence of bits are properly erased, their content will be
11111111111111111111111
Now, if the data
11001000111010101000101
Is written to this area, the sequence would become:
11001000111010101000101
But if the write process is interrupted before the cells have changed their logical state, the area will remain:
11111111111111111111111
However, the pale digits may be partially in transition, and there is no way to know that by reading the data.
Now, if the following new data is written to this area:
10101001001110101110101
The result will be:
10101010001110101110101
meaning that all the pale “1”'s are partially converted to “0” and may unintentionally change their logical state. For this reason, it is essential that data never be written into an interrupted page.
One prior art method for such assuring that data is not written to an interrupted page is to always read the page to be written and compare its content to the value “111 . . . 1”, which is the expected readout of an erased page. As explained above, this is not a reliable method, as a page may be poorly written due an interrupted process.
Another prior art method for such assurance is to always write only into fresh blocks. In other words, whenever moving to write in a different block, one starts with a fully erased block. If one fills only half of a block and moves elsewhere, one is not allowed to return to the half empty block and continue where previously stopped. A new erased block is allocated, any previous data from the previous block is moved into the new block and the new data is then written therein. This solves the problem, but is very inefficient.
There is therefore a widely recognized need for, and it would be highly advantageous to have a method for writing into a flash memory device that ensures that data is written only to a page that has not been interrupted in writing, without the poor reliability or inefficiency of the prior art methods.